﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FindGreatestLinkedNode.Question;

namespace FindGreatestLinkedNode.Answer
{
    class Bob : IFindNearestGreatestNodeInBinaryTree
    {

        List<PrivateNode> list;
        public int? FindNearestGreatestNode(Node root, int k)
        {
            this.list = new List<PrivateNode>();
            Search(root, null);

            foreach (var node in list)
            {
                
                if (node.Current.Data == k)
                {
                    var res = node.Current.Data;
                    if (node.Parent != null)
                        res = Math.Max(res, node.Parent.Data);

                    if (node.Left != null)
                        res = Math.Max(res, node.Left.Data);

                    if (node.Right != null)
                        res = Math.Max(res, node.Right.Data);

                    return res;
                }
            }

            return null;
        }

        public void Search(Node root, Node parent)
        {
            if (root == null)
            {
                return;
            }

            PrivateNode cur = new PrivateNode();
            cur.Current = root;
            cur.Parent = parent;
            cur.Left = root.LeftChild;
            cur.Right = root.RightChild;

            list.Add(cur);

            if (root.LeftChild != null)
            {
                Search(root.LeftChild, root);
            }
            if (root.RightChild != null)
            {
                Search(root.RightChild, root);
            }
        }


    }

    class PrivateNode
    {
        public Node Parent;
        public Node Current;
        public Node Left;
        public Node Right;
    }
}
